home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 9 / Night Owl CD-ROM (NOPV9) (Night Owl Publisher) (1993).ISO / 009a / snpd0493.zip / BMHSRCH.C < prev    next >
C/C++ Source or Header  |  1993-04-05  |  2KB  |  66 lines
  1. /*
  2. **  Case-sensitive Boyer-Moore-Horspool pattern match
  3. **
  4. **  public domain by Raymond Gardner 7/92
  5. **
  6. **  limitation: pattern length + string length must be less than 32767
  7. */
  8.  
  9. #include <stddef.h>
  10. #include <string.h>
  11.  
  12. typedef unsigned char uchar;
  13.  
  14. #define LARGE 32767
  15.  
  16. static int patlen;
  17. static int skip[256];
  18. static int skip2;
  19. static uchar *pat;
  20.  
  21. void bmh_init(const char *pattern)
  22. {
  23.           int i, lastpatchar;
  24.  
  25.           pat = (uchar *)pattern;
  26.           patlen = strlen(pattern);
  27.           for (i = 0; i < 256; ++i)
  28.                 skip[i] = patlen;
  29.           for (i = 0; i < patlen; ++i)
  30.                 skip[pat[i]] = patlen - i - 1;
  31.           lastpatchar = pat[patlen - 1];
  32.           skip[lastpatchar] = LARGE;
  33.           skip2 = patlen;                 /* Horspool's fixed second shift */
  34.           for (i = 0; i < patlen - 1; ++i)
  35.           {
  36.                 if (pat[i] == lastpatchar)
  37.                       skip2 = patlen - i - 1;
  38.           }
  39. }
  40.  
  41. char *bmh_search(const char *string, const int stringlen)
  42. {
  43.       int i, j;
  44.       char *s;
  45.  
  46.       i = patlen - 1 - stringlen;
  47.       if (i >= 0)
  48.             return NULL;
  49.       string += stringlen;
  50.       for ( ;; )
  51.       {
  52.             while ( (i += skip[((uchar *)string)[i]]) < 0 )
  53.                   ;                           /* mighty fast inner loop */
  54.             if (i < (LARGE - stringlen))
  55.                   return NULL;
  56.             i -= LARGE;
  57.             j = patlen - 1;
  58.             s = (char *)string + (i - j);
  59.             while (--j >= 0 && s[j] == pat[j])
  60.                   ;
  61.             if ( j >= 0 )
  62.                   i += skip2;
  63.             else  return s;
  64.       }
  65. }
  66.